We study a game with \emph{strategic} vendors who own multiple items and asingle buyer with a submodular valuation function. The goal of the vendors isto maximize their revenue via pricing of the items, given that the buyer willbuy the set of items that maximizes his net payoff. We show this game may not always have a pure Nash equilibrium, in contrast toprevious results for the special case where each vendor owns a single item. Wedo so by relating our game to an intermediate, discrete game in which thevendors only choose the available items, and their prices are set exogenouslyafterwards. We further make use of the intermediate game to provide tight bounds on theprice of anarchy for the subset games that have pure Nash equilibria; we findthat the optimal PoA reached in the previous special cases does not hold, butonly a logarithmic one. Finally, we show that for a special case of submodular functions, efficientpure Nash equilibria always exist.
展开▼
